package leetcode20211016;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LUYAO
 * Date: 2021-10-16
 * Time: 12:39
 */
public class Sort16 {
}

class Solution16 {
    public int[] getLeastNumbers(int[] arr, int k) {
        quicksort(arr, 0, arr.length - 1);
        return Arrays.copyOf(arr, k);
    }

    private void quicksort(int[] arr,int l, int r){
        // 子数组长度为 1 时终止递归
        if(l >= r) return;
        // 哨兵划分操作（以 arr[l] 作为基准数）
        int i = l,j = r;
        while(i < j){
            while(i < j && arr[j] >= arr[l]) j--;//为什么一定要先j--
            while(i < j && arr[i] <= arr[l]) i++;

            swap(arr,i,j);
        }
        swap(arr,i,l);

        // 递归左（右）子数组执行哨兵划分
        quicksort(arr,l,i-1);
        quicksort(arr,i+1,r);


    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }


}

//找数据流的中位数
class MedianFinder {
    ArrayList list;

    /** initialize your data structure here. */
    public MedianFinder() {
        ArrayList<Double> list = new ArrayList<>();

    }

    public void addNum(int num) {
        list.add(num);

    }

    public double findMedian() {
        Collections.sort(list);
        if(list.size() %2 == 1){
            return (double) list.get(list.size()/2);
        }else{
            return (double) 1;
        }

    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
//求1+2+...+n 短路效应，前面不满足就不会后面再递归
class Solution1663 {
    public int sumNums(int n) {
        boolean x = n > 1 && (n += sumNums(n-1)) > 0;
        return n;
    }
}

//n次幂


